Plasarea automată a etichetelor

Plasarea automată a etichetelor, numită și plasarea textului sau plasarea numelui, cuprinde metodele computerizate de plasare automată a etichetelor pe o hartă sau pe o diagramă. Acest lucru este legat de proiectarea tipografică a acestor etichete.

Caracteristicile tipice descrise pe o hartă geografică sunt: caracteristicile liniei (de ex. Drumuri), caracteristicile zonei (țări, parcele, păduri, lacuri etc.) și caracteristicile punctului (sate, orașe etc.). În plus față de descrierea caracteristicilor hărții într-o manieră exactă din punct de vedere geografic, este de o importanță critică să plasați numele care identifică aceste caracteristici, într-un mod în care cititorul să știe instantaneu ce nume descrie ce caracteristică.

Plasarea automată a textului este una dintre cele mai dificile, complexe și care consumă mult timp în realizarea hărților și GIS (Geographic Information System). Alte tipuri de grafică generată de computer - cum ar fi diagrame, grafice etc. - necesită plasarea corectă a etichetelor, fără a menționa desenele tehnice și programele profesionale care produc aceste desene și diagrame, cum ar fi foile de calcul (de ex. Microsoft Excel) sau programe software de calcul (de ex Mathematica^⁠(d)).

Etichetele plasate naiv se suprapun excesiv, rezultând o hartă care este dificil sau chiar imposibil de citit. Prin urmare, un sistem GIS trebuie să permită câteva plasări posibile ale fiecărei etichete și, adesea, și o opțiune de redimensionare, rotire sau chiar eliminare (suprimare) a etichetei. Apoi, selectează un set de destinații de plasare care are ca rezultat cea mai mică suprapunere și cu alte proprietăți dorite. Pentru toate configurările, cu excepția celor mai banale, problema este NP-hard.

Algoritmi bazați pe reguli

Algoritmii bazați pe reguli încearcă să imite un cartograf uman experimentat. De-a lungul secolelor, cartografii au dezvoltat arta cartografierii și a plasării etichetelor. De exemplu, un cartograf cu experiență repetă numele drumurilor de mai multe ori pentru drumuri lungi, în loc să le așeze o dată sau de exemplu, în cazul orașului Constanta, reprezentat de un punct foarte apropiat de țărm, cartograful ar plasa eticheta „Constanta” deasupra teren pentru a sublinia că este un oraș de coastă. ^[1]

Cartografii lucrează pe baza convențiilor și regulilor acceptate, precum cele detaliate de cartograful elvețian Eduard Imhof în 1962.^[2] De exemplu, New York City, Viena, Berlin, Paris sau Tokyo trebuie să apară pe hărțile țărilor, deoarece acestea sunt etichete cu prioritate ridicată. Odată ce acestea sunt plasate, cartograful plasează următoarea cea mai importantă clasă de etichete, de exemplu drumuri majore, râuri și alte orașe mari. În fiecare etapă se asigură că (1) textul este plasat într-un mod în care cititorul îl asociază cu ușurință cu caracteristica și (2) eticheta nu se suprapune cu cele deja plasate pe hartă.

Algoritmi de optimizare locală

Cel mai simplu algoritm lacom plasează etichete consecutive pe hartă în poziții care duc la o suprapunere minimă a etichetelor. Rezultatele sale nu sunt perfecte chiar și pentru probleme foarte simple, dar este extrem de rapid.

Algoritmii puțin mai complecși se bazează pe optimizarea locală pentru a atinge un optim local al unei funcții de evaluare a plasării - în fiecare iterație plasarea unei singure etichete este mutată într-o altă poziție și, dacă îmbunătățește rezultatul, mutarea este păstrată. Funcționează în mod rezonabil pentru hărțile care nu sunt etichetate prea dens. Variații puțin mai complexe încercați să mutați 2 sau mai multe etichete în același timp. Algoritmul se încheie după ce a atins un nivel optim local.

Un algoritm simplu - recoacere simulată^⁠(d) - dă rezultate bune cu performanțe relativ bune. Funcționează ca optimizarea locală, dar poate păstra o schimbare chiar dacă înrăutățește rezultatul. Șansa de a păstra o astfel de schimbare este $\exp {\frac {-\Delta E}{T}}$ , Unde $\Delta E$ este schimbarea funcției de evaluare și $T$ este temperatura . Temperatura este redusă treptat în conformitate cu programul de recoacere. Când temperatura este ridicată, recoacerea simulată efectuează modificări aproape aleatorii la plasarea etichetei, putând scăpa de un optim local. Mai târziu, când sperăm că a fost găsit un optim local foarte bun, acesta se comportă într-un mod similar cu optimizarea locală. Principalele provocări în dezvoltarea unei soluții simulate de recoacere sunt alegerea unei bune funcții de evaluare și a unui program bun de recoacere. În general, răcirea prea rapidă va degrada soluția, iar răcirea prea lentă va degrada performanța, dar programul este de obicei un algoritm destul de complex, cu mai mult de un singur parametru.

O altă clasă de algoritmi de căutare directă sunt diferiții algoritmi evolutivi, de exemplu algoritmi genetici.

Algoritmi împărțiți și cuceriți

O optimizare simplă care este importantă pe hărțile reale este împărțirea unui set de etichete în seturi mai mici care pot fi rezolvate independent. Două etichete sunt rivale dacă se pot suprapune într-una dintre destinațiile de plasare posibile. Închiderea tranzitivă a acestei relații împarte setul de etichete în seturi posibil mult mai mici. Pe hărțile etichetate uniform și dens, de obicei setul unic va conține majoritatea etichetelor, iar pe hărțile pentru care etichetarea nu este uniformă poate aduce beneficii de performanță foarte mari. De exemplu, atunci când etichetează o hartă a lumii, America este etichetată independent de Eurasia etc.

2-algoritmi de satisfacție

Dacă o problemă de etichetare a hărții poate fi redusă la o situație în care fiecare etichetă rămasă are doar două poziții potențiale în care poate fi plasată, atunci poate fi rezolvată eficient utilizând o instanță de 2-satisfacție pentru a găsi o plasare evitând orice perechi conflictuale de plasamente; pe acest principiu se bazează mai mulți algoritmi de plasare a etichetelor exacte și aproximative pentru tipuri mai complexe de probleme.^[3]

Alți algoritmi

Algoritmii de plasare automată a etichetelor pot folosi oricare dintre algoritmi pentru a găsi setul maxim disjunct din setul de etichete potențiale. Pot fi utilizați și alți algoritmi, cum ar fi diverse soluții grafice, programarea în întregime etc.

Note

^ Slocum, Terry (2010). Thematic Cartography and Geovisualization. Upper Saddle River, NJ: Pearson. p. 576. ISBN 978-0-13-801006-5.
^ Imhof, Eduard, “Die Anordnung der Namen in der Karte,” Annuaire International de Cartographie II, Orell-Füssli Verlag, Zürich, 93-129, 1962. English Translation: "Positioning Names on Maps," The American Cartographer, V.2 #2 (1975), pp.128-144
^ Doddi, Srinivas; Marathe, Madhav V.; Mirzaian, Andy; Moret, Bernard M. E.; Zhu, Binhai (1997), „Map labeling and its generalizations”, Proc. 8th ACM-SIAM Symp. Discrete Algorithms (SODA), pp. 148–157 ; Formann, M.; Wagner, F. (1991), „A packing problem with applications to lettering of maps”, Proc. 7th ACM Symp. Computational Geometry, pp. 281–288 ; Poon, Chung Keung; Zhu, Binhai; Chin, Francis (1998), „A polynomial time solution for labeling a rectilinear map”, Information Processing Letters, 65 (4), pp. 201–207, doi:10.1016/S0020-0190(98)00002-7 ; Wagner, Frank; Wolff, Alexander (1997), „A practical map labeling algorithm”, Computational Geometry: Theory and Applications^⁠(d), 7 (5–6), pp. 387–404, doi:10.1016/S0925-7721(96)00007-7 .

Bibliografie

Freeman, H., Prelucrarea datelor hărților și problema adnotării, Proc. A 3-a conf. Scandinavă privind analiza imaginilor, Chartwell-Bratt Ltd. Copenhaga, 1983.
Ahn, J. și Freeman, H., „Un program pentru plasarea automată a numelor”, Proc. AUTO-CARTO 6, Ottawa, 1983. 444–455.
Freeman, H., „Computer Name Placement”, cap. 29, în Geographic Information Systems, 1, DJ Maguire, MF Goodchild și DW Rhind, John Wiley, New York, 1991, 449–460.
Podolskaya NN Algoritmi de deconflicție de etichete automate pentru aplicații grafice interactive. Tehnologii informaționale (ISSN 1684-6400), 9, 2007, p. 45-50. În rusă: Подольская Н.Н. Алгоритмы автоматического отброса формуляров для интерак тивных графических приложений. Информационные технологии, 9, 2007, с. 45-50.
Kameda, T. și K. Imai. 2003. Plasarea etichetei hărții pentru puncte și curbe. IEICE Tranzacțiile fundamentelor comunicațiilor electronice și științelor computerizate. E86A (4): 835-840.
Ribeiro Glaydston și Luiz Lorena. 2006. Euristică pentru probleme de plasare a etichetelor cartografice. Calculatoare și Geoștiințe. 32: 739–748.
Wagner, F., A. Wolff, V. Kapoor și T. Strijk. 2001. Trei reguli sunt suficiente pentru o bună plasare a etichetelor. Algorithmica. 30: 334–349.

Legături externe

Site-ul de etichetare a hărților lui Alexander Wolff Arhivat în 30 ianuarie 2017, la Wayback Machine.
Bibliografia de etichetare a hărților Arhivat în 24 aprilie 2017, la Wayback Machine.
Plasarea etichetelor
Un studiu empiric al algoritmilor pentru plasarea etichetei punct-caracteristică

[1] Slocum, Terry (2010). Thematic Cartography and Geovisualization. Upper Saddle River, NJ: Pearson. p. 576. ISBN 978-0-13-801006-5.

[imhof-2] Imhof, Eduard, “Die Anordnung der Namen in der Karte,” Annuaire International de Cartographie II, Orell-Füssli Verlag, Zürich, 93-129, 1962. English Translation: "Positioning Names on Maps," The American Cartographer, V.2 #2 (1975), pp.128-144

[3] Doddi, Srinivas; Marathe, Madhav V.; Mirzaian, Andy; Moret, Bernard M. E.; Zhu, Binhai (1997), „Map labeling and its generalizations”, Proc. 8th ACM-SIAM Symp. Discrete Algorithms (SODA), pp. 148–157 ; Formann, M.; Wagner, F. (1991), „A packing problem with applications to lettering of maps”, Proc. 7th ACM Symp. Computational Geometry, pp. 281–288 ; Poon, Chung Keung; Zhu, Binhai; Chin, Francis (1998), „A polynomial time solution for labeling a rectilinear map”, Information Processing Letters, 65 (4), pp. 201–207, doi:10.1016/S0020-0190(98)00002-7 ; Wagner, Frank; Wolff, Alexander (1997), „A practical map labeling algorithm”, Computational Geometry: Theory and Applications^⁠(d), 7 (5–6), pp. 387–404, doi:10.1016/S0925-7721(96)00007-7 .

[1]

[2]

[3]